package problem;

import java.util.List;
/*给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。*/
public class S_120 {
    //1.常规DFS超时
    class Solution {
        int min=Integer.MAX_VALUE;
        public void dfs(List<List<Integer>> triangle,int depth,int value,int index){
            if(depth==triangle.size()) return;
            if(depth==triangle.size()-1&&value+triangle.get(depth).get(index)<min)
                min=value+triangle.get(depth).get(index);
            dfs(triangle,depth+1,value+triangle.get(depth).get(index),index);
            dfs(triangle,depth+1,value+triangle.get(depth).get(index),index+1);

        }
        public int minimumTotal(List<List<Integer>> triangle) {
            dfs(triangle,0,0,0);
            return min;
        }
    }

    /*    int minimumTotal(vector<vector<int>>& triangle) {
        for(int i = triangle.size() - 1; i >= 1; i--)
            for(int j = 0; j < triangle[i - 1].size(); j++)
                triangle[i - 1][j] = triangle[i - 1][j] + min(triangle[i][j], triangle[i][j + 1]);
        return triangle[0][0];
    }*/

    //2.递归自顶向下
    class Solution1{
        int row;
        public int minimumTotal(List<List<Integer>> triangle){
            row=triangle.size();
            return helper(0,0,triangle);
        }
        //当前位置到最下面的距离
        private int helper(int level,int c,List<List<Integer>> triangle){
            if(level==row-1) return triangle.get(level).get(c);
            int left=helper(level+1,c,triangle);
            int right=helper(level+1,c+1,triangle);
            return Math.min(left,right)+triangle.get(level).get(c);
        }
    }

    //3.自顶向下，记忆化DP
    class Solution2{
        int row;
        Integer [][]memo;
        public int minimumTotal(List<List<Integer>> triangle){
            row=triangle.size();
            memo=new Integer[row][row];
            return helper(0,0,triangle);
        }
        private int helper(int level,int c,List<List<Integer>> triangle){
            if(memo[level][c]!=null) return memo[level][c];
            if(level==row-1) return memo[level][c]=triangle.get(level).get(c);
            int left=helper(level+1,c,triangle);
            int right=helper(level+1,c+1,triangle);
            return memo[level][c]=Math.min(left,right)+triangle.get(level).get(c);
        }
    }

    //4.自底向上DP
    class Solution3{
        public int minimumTotal(List<List<Integer>> triangle){
            int row=triangle.size();
            int []minlen=new int[row+1];
            for(int level=row-1;level>=0;level--){
                for(int c=0;c<=level;c++){
                    minlen[c] = Math.min(minlen[c], minlen[c+1]) + triangle.get(level).get(c);
                }
            }
            return minlen[0];
        }
    }
}
